"""
@Project ：leetocde 
@File    ：147.对列表进行插入排序.py
@Author  ：zhupp
@Date    ：2024/12/2 11:50 
"""
from typing import Optional

"""
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
"""


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy_node = ListNode()
        dummy_node.next = head
        # 待排序的节点
        cur_node = head.next
        # 已排好序的链表的最后一个节点
        last_sorted_node = head
        # 一直循环到没有待排序的节点
        while cur_node:
            # 如果待排序的节点值大于有序链表的尾节点值，则此节点替换为有序链表的尾节点
            if cur_node.val >= last_sorted_node.val:
                last_sorted_node = last_sorted_node.next
            else:
                # prev_node.next为cur_node插入的地方
                prev_node = dummy_node
                # 找到可插入的地方
                while prev_node.next.val <= cur_node.val:
                    prev_node = prev_node.next
                # 先将待排序节点归到有序链表中
                last_sorted_node.next = cur_node.next
                # 使cur_node指向prev_node的下一个节点
                cur_node.next = prev_node.next
                # 再让prev_node的下一个节点指向cur_node 一次排序完成
                prev_node.next = cur_node
            # 一次排序完成后 将有序链表后面的一个节点变为待排序节点
            cur_node = last_sorted_node.next
        return dummy_node.next


s = Solution()
